// poj1284
// 题意：给定一些素数p(<65536)，对于每个素数输出它原根的个数。
//
// 题解：这涉及到一些原根的性质，其实这题可以更一般些，输入不一定要是
//       素数。假设输入正整数m，如果模m有原根，那么其原根个数是
//       phi(phi(m))，phi是欧拉函数，对于素数p个数就是phi(p-1)。
//       这里补充一个性质，对于正整数m有原根当且仅当，m=2, 4, p^a, 2*p^a,
//       其中p是奇素数。
//
//       关于欧拉函数计算，可以利用欧拉函数积性推导的展开式，
//       phi(n)=n*PI(1-1/p), p是n的素因子。然后单个可以用试除法，如果要求
//       [1..n]所有欧拉函数，可以用筛法。
//
#include <iostream>

int const maxn = 65537;
int phi[maxn];
bool not_prime[maxn];

void init_phi()
{
	for (int i = 1; i < maxn; i++) phi[i] = i;
	for (int i = 2; i < maxn; i++) {
		if (not_prime[i]) continue;
		phi[i] = i - 1;
		for (int j = 2 * i; j < maxn; j += i) {
			not_prime[j] = true;
			phi[j] /= i;
			phi[j] *= (i - 1);
		}
	}
}

int main()
{
	init_phi();
	for (int p; std::cin >> p; )
		std::cout << phi[phi[p]] << '\n';
}

